package com.nulldev.util.internal.backport.arrays;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

import com.nulldev.util.JVM.JVM;
import com.nulldev.util.internal.backport.concurrency9.concurrent.ForkJoinPool;

public class BackportArrays {

	/**
	 * The minimum array length below which a parallel sorting algorithm will not
	 * further partition the sorting task. Using smaller sizes typically results in
	 * memory contention across tasks that makes parallel speedups unlikely.
	 */
	private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;

	/**
	 * A comparator that implements the natural ordering of a group of mutually
	 * comparable elements. May be used when a supplied comparator is null. To
	 * simplify code-sharing within underlying implementations, the compare method
	 * only declares type Object for its second argument.
	 *
	 * Arrays class implementor's note: It is an empirical matter whether
	 * ComparableTimSort offers any performance benefit over TimSort used with this
	 * comparator. If not, you are better off deleting or bypassing
	 * ComparableTimSort. There is currently no empirical case for separating them
	 * for parallel sorting, so all public Object parallelSort methods use the same
	 * comparator based implementation.
	 */
	static final class NaturalOrder implements Comparator<Object> {
		@SuppressWarnings("unchecked")
		public int compare(Object first, Object second) {
			return ((Comparable<Object>) first).compareTo(second);
		}

		static final NaturalOrder INSTANCE = new NaturalOrder();
	}

	/**
	 * Checks that {@code fromIndex} and {@code toIndex} are in the range and throws
	 * an exception if they aren't.
	 */
	private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
		if (fromIndex > toIndex) {
			throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
		}
		if (fromIndex < 0) {
			throw new ArrayIndexOutOfBoundsException(fromIndex);
		}
		if (toIndex > arrayLength) {
			throw new ArrayIndexOutOfBoundsException(toIndex);
		}
	}

	/**
	 * Sorts the specified array of objects according to the order induced by the
	 * specified comparator. All elements in the array must be <i>mutually
	 * comparable</i> by the specified comparator (that is,
	 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} for any
	 * elements {@code e1} and {@code e2} in the array).
	 *
	 * <p>
	 * This sort is guaranteed to be <i>stable</i>: equal elements will not be
	 * reordered as a result of the sort.
	 *
	 * @implNote The sorting algorithm is a parallel sort-merge that breaks the
	 *           array into sub-arrays that are themselves sorted and then merged.
	 *           When the sub-array length reaches a minimum granularity, the
	 *           sub-array is sorted using the appropriate
	 *           {@link Arrays#sort(Object[]) Arrays.sort} method. If the length of
	 *           the specified array is less than the minimum granularity, then it
	 *           is sorted using the appropriate {@link Arrays#sort(Object[])
	 *           Arrays.sort} method. The algorithm requires a working space no
	 *           greater than the size of the original array. The
	 *           {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to
	 *           execute any parallel tasks.
	 *
	 * @param <T> the class of the objects to be sorted
	 * @param a   the array to be sorted
	 * @param cmp the comparator to determine the order of the array. A {@code null}
	 *            value indicates that the elements' {@linkplain Comparable natural
	 *            ordering} should be used.
	 * @throws ClassCastException       if the array contains elements that are not
	 *                                  <i>mutually comparable</i> using the
	 *                                  specified comparator
	 * @throws IllegalArgumentException (optional) if the comparator is found to
	 *                                  violate the {@link java.util.Comparator}
	 *                                  contract
	 *
	 * @since 1.8
	 */
	@SuppressWarnings("unchecked")
	public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
		if (a == null || a.length <= 1) {
			return;
		} else if (cmp == null)
			cmp = NaturalOrder.INSTANCE;
		int n = a.length, p, g;
		if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
			TimSort.sort(a, 0, n, cmp, null, 0, 0);
		else
			new ArraysParallelSortHelpers.FJObject.Sorter<T>(null, a, (T[]) Array.newInstance(a.getClass().getComponentType(), n), 0, n, 0,
					((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
	}

	/**
	 * Sorts the specified range of the specified array of objects according to the
	 * order induced by the specified comparator. The range to be sorted extends
	 * from index {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
	 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All
	 * elements in the range must be <i>mutually comparable</i> by the specified
	 * comparator (that is, {@code c.compare(e1, e2)} must not throw a
	 * {@code ClassCastException} for any elements {@code e1} and {@code e2} in the
	 * range).
	 *
	 * <p>
	 * This sort is guaranteed to be <i>stable</i>: equal elements will not be
	 * reordered as a result of the sort.
	 *
	 * <p>
	 * Implementation note: This implementation is a stable, adaptive, iterative
	 * mergesort that requires far fewer than n lg(n) comparisons when the input
	 * array is partially sorted, while offering the performance of a traditional
	 * mergesort when the input array is randomly ordered. If the input array is
	 * nearly sorted, the implementation requires approximately n comparisons.
	 * Temporary storage requirements vary from a small constant for nearly sorted
	 * input arrays to n/2 object references for randomly ordered input arrays.
	 *
	 * <p>
	 * The implementation takes equal advantage of ascending and descending order in
	 * its input array, and can take advantage of ascending and descending order in
	 * different parts of the the same input array. It is well-suited to merging two
	 * or more sorted arrays: simply concatenate the arrays and sort the resulting
	 * array.
	 *
	 * <p>
	 * The implementation was adapted from Tim Peters's list sort for Python
	 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
	 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic Sorting and
	 * Information Theoretic Complexity", in Proceedings of the Fourth Annual
	 * ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
	 *
	 * @param <T>       the class of the objects to be sorted
	 * @param a         the array to be sorted
	 * @param fromIndex the index of the first element (inclusive) to be sorted
	 * @param toIndex   the index of the last element (exclusive) to be sorted
	 * @param c         the comparator to determine the order of the array. A
	 *                  {@code null} value indicates that the elements'
	 *                  {@linkplain Comparable natural ordering} should be used.
	 * @throws ClassCastException             if the array contains elements that
	 *                                        are not <i>mutually comparable</i>
	 *                                        using the specified comparator.
	 * @throws IllegalArgumentException       if {@code fromIndex > toIndex} or
	 *                                        (optional) if the comparator is found
	 *                                        to violate the {@link Comparator}
	 *                                        contract
	 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
	 *                                        {@code toIndex > a.length}
	 */
	public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) {
		if (c == null) {
			sort(a, fromIndex, toIndex);
		} else {
			rangeCheck(a.length, fromIndex, toIndex);
			if (LegacyMergeSort.userRequested)
				legacyMergeSort(a, fromIndex, toIndex, c);
			else
				TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
		}
	}

	/** To be removed in a future release. */
	private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) {
		T[] aux = Arrays.copyOfRange(a, fromIndex, toIndex);
		if (c == null)
			mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
		else
			mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
	}

	/**
	 * Sorts the specified range of the specified array of objects into ascending
	 * order, according to the {@linkplain Comparable natural ordering} of its
	 * elements. The range to be sorted extends from index {@code fromIndex},
	 * inclusive, to index {@code toIndex}, exclusive. (If
	 * {@code fromIndex==toIndex}, the range to be sorted is empty.) All elements in
	 * this range must implement the {@link Comparable} interface. Furthermore, all
	 * elements in this range must be <i>mutually comparable</i> (that is,
	 * {@code e1.compareTo(e2)} must not throw a {@code ClassCastException} for any
	 * elements {@code e1} and {@code e2} in the array).
	 *
	 * <p>
	 * This sort is guaranteed to be <i>stable</i>: equal elements will not be
	 * reordered as a result of the sort.
	 *
	 * <p>
	 * Implementation note: This implementation is a stable, adaptive, iterative
	 * mergesort that requires far fewer than n lg(n) comparisons when the input
	 * array is partially sorted, while offering the performance of a traditional
	 * mergesort when the input array is randomly ordered. If the input array is
	 * nearly sorted, the implementation requires approximately n comparisons.
	 * Temporary storage requirements vary from a small constant for nearly sorted
	 * input arrays to n/2 object references for randomly ordered input arrays.
	 *
	 * <p>
	 * The implementation takes equal advantage of ascending and descending order in
	 * its input array, and can take advantage of ascending and descending order in
	 * different parts of the the same input array. It is well-suited to merging two
	 * or more sorted arrays: simply concatenate the arrays and sort the resulting
	 * array.
	 *
	 * <p>
	 * The implementation was adapted from Tim Peters's list sort for Python
	 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
	 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic Sorting and
	 * Information Theoretic Complexity", in Proceedings of the Fourth Annual
	 * ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
	 *
	 * @param a         the array to be sorted
	 * @param fromIndex the index of the first element (inclusive) to be sorted
	 * @param toIndex   the index of the last element (exclusive) to be sorted
	 * @throws IllegalArgumentException       if {@code fromIndex > toIndex} or
	 *                                        (optional) if the natural ordering of
	 *                                        the array elements is found to violate
	 *                                        the {@link Comparable} contract
	 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
	 *                                        {@code toIndex > a.length}
	 * @throws ClassCastException             if the array contains elements that
	 *                                        are not <i>mutually comparable</i>
	 *                                        (for example, strings and integers).
	 */
	public static void sort(Object[] a, int fromIndex, int toIndex) {
		rangeCheck(a.length, fromIndex, toIndex);
		if (LegacyMergeSort.userRequested)
			legacyMergeSort(a, fromIndex, toIndex);
		else
			ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
	}

	/** To be removed in a future release. */
	private static void legacyMergeSort(Object[] a, int fromIndex, int toIndex) {
		Object[] aux = Arrays.copyOfRange(a, fromIndex, toIndex);
		mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
	}

	/**
	 * Sorts the specified array of objects according to the order induced by the
	 * specified comparator. All elements in the array must be <i>mutually
	 * comparable</i> by the specified comparator (that is,
	 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} for any
	 * elements {@code e1} and {@code e2} in the array).
	 *
	 * <p>
	 * This sort is guaranteed to be <i>stable</i>: equal elements will not be
	 * reordered as a result of the sort.
	 *
	 * <p>
	 * Implementation note: This implementation is a stable, adaptive, iterative
	 * mergesort that requires far fewer than n lg(n) comparisons when the input
	 * array is partially sorted, while offering the performance of a traditional
	 * mergesort when the input array is randomly ordered. If the input array is
	 * nearly sorted, the implementation requires approximately n comparisons.
	 * Temporary storage requirements vary from a small constant for nearly sorted
	 * input arrays to n/2 object references for randomly ordered input arrays.
	 *
	 * <p>
	 * The implementation takes equal advantage of ascending and descending order in
	 * its input array, and can take advantage of ascending and descending order in
	 * different parts of the the same input array. It is well-suited to merging two
	 * or more sorted arrays: simply concatenate the arrays and sort the resulting
	 * array.
	 *
	 * <p>
	 * The implementation was adapted from Tim Peters's list sort for Python
	 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
	 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic Sorting and
	 * Information Theoretic Complexity", in Proceedings of the Fourth Annual
	 * ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
	 *
	 * @param <T> the class of the objects to be sorted
	 * @param a   the array to be sorted
	 * @param c   the comparator to determine the order of the array. A {@code null}
	 *            value indicates that the elements' {@linkplain Comparable natural
	 *            ordering} should be used.
	 * @throws ClassCastException       if the array contains elements that are not
	 *                                  <i>mutually comparable</i> using the
	 *                                  specified comparator
	 * @throws IllegalArgumentException (optional) if the comparator is found to
	 *                                  violate the {@link Comparator} contract
	 */
	public static <T> void sort(T[] a, Comparator<? super T> c) {
		if (a == null || a.length <= 1) {
			return;
		} else if (c == null) {
			sort(a);
		} else {
			if (LegacyMergeSort.userRequested)
				legacyMergeSort(a, c);
			else
				TimSort.sort(a, 0, a.length, c, null, 0, 0);
		}
	}

	/**
	 * Sorts the specified array of objects into ascending order, according to the
	 * {@linkplain Comparable natural ordering} of its elements. All elements in the
	 * array must implement the {@link Comparable} interface. Furthermore, all
	 * elements in the array must be <i>mutually comparable</i> (that is,
	 * {@code e1.compareTo(e2)} must not throw a {@code ClassCastException} for any
	 * elements {@code e1} and {@code e2} in the array).
	 *
	 * <p>
	 * This sort is guaranteed to be <i>stable</i>: equal elements will not be
	 * reordered as a result of the sort.
	 *
	 * <p>
	 * Implementation note: This implementation is a stable, adaptive, iterative
	 * mergesort that requires far fewer than n lg(n) comparisons when the input
	 * array is partially sorted, while offering the performance of a traditional
	 * mergesort when the input array is randomly ordered. If the input array is
	 * nearly sorted, the implementation requires approximately n comparisons.
	 * Temporary storage requirements vary from a small constant for nearly sorted
	 * input arrays to n/2 object references for randomly ordered input arrays.
	 *
	 * <p>
	 * The implementation takes equal advantage of ascending and descending order in
	 * its input array, and can take advantage of ascending and descending order in
	 * different parts of the the same input array. It is well-suited to merging two
	 * or more sorted arrays: simply concatenate the arrays and sort the resulting
	 * array.
	 *
	 * <p>
	 * The implementation was adapted from Tim Peters's list sort for Python
	 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
	 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic Sorting and
	 * Information Theoretic Complexity", in Proceedings of the Fourth Annual
	 * ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
	 *
	 * @param a the array to be sorted
	 * @throws ClassCastException       if the array contains elements that are not
	 *                                  <i>mutually comparable</i> (for example,
	 *                                  strings and integers)
	 * @throws IllegalArgumentException (optional) if the natural ordering of the
	 *                                  array elements is found to violate the
	 *                                  {@link Comparable} contract
	 */
	public static void sort(Object[] a) {
		if (LegacyMergeSort.userRequested)
			legacyMergeSort(a);
		else
			ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
	}

	/** To be removed in a future release. */
	private static void legacyMergeSort(Object[] a) {
		Object[] aux = a.clone();
		mergeSort(aux, a, 0, a.length, 0);
	}

	/**
	 * Old merge sort implementation can be selected (for compatibility with broken
	 * comparators) using a system property. Cannot be a static boolean in the
	 * enclosing class due to circular dependencies. To be removed in a future
	 * release.
	 */
	static final class LegacyMergeSort {
		private static final boolean userRequested = JVM.version() <= 16f
				? java.security.AccessController.doPrivileged(new sun.security.action.GetBooleanAction("java.util.Arrays.useLegacyMergeSort")).booleanValue()
				: false;
	}

	/** To be removed in a future release. */
	private static <T> void legacyMergeSort(final T[] a, final Comparator<? super T> c) {
		T[] aux = a.clone();
		if (c == null)
			mergeSort(aux, a, 0, a.length, 0);
		else
			mergeSort(aux, a, 0, a.length, 0, c);
	}

	/**
	 * Tuning parameter: list size at or below which insertion sort will be used in
	 * preference to mergesort. To be removed in a future release.
	 */
	private static final int INSERTIONSORT_THRESHOLD = 7;

	/**
	 * Src is the source array that starts at index 0 Dest is the (possibly larger)
	 * array destination with a possible offset low is the index in dest to start
	 * sorting high is the end index in dest to end sorting off is the offset to
	 * generate corresponding low, high in src To be removed in a future release.
	 */
	@SuppressWarnings(
		{ "unchecked", "rawtypes" })
	private static void mergeSort(final Object[] src, final Object[] dest, int low, int high, final int off) {
		int length = high - low;

		// Insertion sort on smallest arrays
		if (length < INSERTIONSORT_THRESHOLD) {
			for (int i = low; i < high; i++)
				for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
					swap(dest, j, j - 1);
			return;
		}

		// Recursively sort halves of dest into src
		int destLow = low;
		int destHigh = high;
		low += off;
		high += off;
		int mid = (low + high) >>> 1;
		mergeSort(dest, src, low, mid, -off);
		mergeSort(dest, src, mid, high, -off);

		// If list is already sorted, just copy from src to dest. This is an
		// optimization that results in faster sorts for nearly ordered lists.
		if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
			System.arraycopy(src, low, dest, destLow, length);
			return;
		}

		// Merge sorted halves (now in src) into dest
		for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
			if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0)
				dest[i] = src[p++];
			else
				dest[i] = src[q++];
		}
	}

	/**
	 * Src is the source array that starts at index 0 Dest is the (possibly larger)
	 * array destination with a possible offset low is the index in dest to start
	 * sorting high is the end index in dest to end sorting off is the offset into
	 * src corresponding to low in dest To be removed in a future release.
	 */
	@SuppressWarnings(
		{ "rawtypes", "unchecked" })
	private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) {
		int length = high - low;

		// Insertion sort on smallest arrays
		if (length < INSERTIONSORT_THRESHOLD) {
			for (int i = low; i < high; i++)
				for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--)
					swap(dest, j, j - 1);
			return;
		}

		// Recursively sort halves of dest into src
		int destLow = low;
		int destHigh = high;
		low += off;
		high += off;
		int mid = (low + high) >>> 1;
		mergeSort(dest, src, low, mid, -off, c);
		mergeSort(dest, src, mid, high, -off, c);

		// If list is already sorted, just copy from src to dest. This is an
		// optimization that results in faster sorts for nearly ordered lists.
		if (c.compare(src[mid - 1], src[mid]) <= 0) {
			System.arraycopy(src, low, dest, destLow, length);
			return;
		}

		// Merge sorted halves (now in src) into dest
		for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
			if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
				dest[i] = src[p++];
			else
				dest[i] = src[q++];
		}
	}

	/**
	 * Swaps x[a] with x[b].
	 */
	private static void swap(final Object[] x, final int a, final int b) {
		final Object t = x[a];
		x[a] = x[b];
		x[b] = t;
	}
}
